【题解】【化学】实验

原题链接

题意：

给$n$个液体分组，要求对于任意不同组液体$i,j$有$gcsd(a_i,a_j)\le x^2$。求最大的组数，满足组数最大的条件下求每组$c_i$的最大值的和。有多组询问，每次给定$x$。

首先，$\operatorname{gcsd}$？那是啥？

按照题目描述里说的，如果定义$h(x)$表示$\sqrt x$的整数因式部分，那么$gcsd(x,y)=h(gcd(x,y))^2$

可以看出这玩意也就等于$gcd(h(x),h(y))^2$。于是原条件就等价于$gcd(h(a_i),h(a_j))\le x$，考虑用$h(a_i)$代替原题中的$a_i$进行计算

另一个问题是求$c_i$，$c_i$定义为$b_i$分解成质因数后最大的指数。

$h(a_i)$和$c_i$都可以用线性筛来求，那么我们的线性筛需要筛四个东西

$s[x]$：$x$的最小质因子

$st[x]$：$x$分解成质因数后$s[x]$的指数

$sm[x]$：$x$分解成质因数后最大的指数

$h[x]$：$\sqrt x$的整数因式部分

std::vector<int> pr;
int s[M], h[M], st[M], sm[M];
void prime() {
	for (int i = 2; i < M; i++) {
		if (!s[i]) { //i是一个质数
			pr.push_back(i);
			s[i] = i;
			st[i] = sm[i] = h[i] = 1;
		}
		for (int j : pr) { //j是i*j的最小质因子
			if (i*j >= M) break;
			s[i*j] = j;
			st[i*j] = (s[i] == j) ? st[i]+1 : 1;
			h[i*j] = (s[i] == j && st[i] & 1) ? h[i]*j : h[i];
			sm[i*j] = std::max(sm[i], st[i*j]);
			if (i % j == 0) break;
		}
	}
}

接下来考虑进一步转化问题。刚才我们说，对于任意不同组液体$i,j$有$gcd(h(a_i),h(a_j))\le x$

再换句话，如果$gcd(h(a_i),h(a_j))> x$，那么$i,j$必须在同一组

这样的描述可以转化为图论模型：每种液体是一个节点，如果$gcd(h(a_i),h(a_j))> x$则节点$i$和$j$之间连一条边。很显然一个连通块内的节点必须在同一组，既然我们要组数最大，那么每个连通块是一组就是最优方案。最大的组数也就是连通块个数，实验得分也很好求，找到每个连通块内最大的$c_i$然后加起来。

举个例子，当$x=2$的时候样例大概长这样（点上的数字就是$a_i$）

于是我们就有了最暴力的算法：对于每个$x$，$O(n^2)$暴力建图，dfs找连通块，时间复杂度$O(mn^2)$。打上这个应该就可以拿30分。

不过，我们发现，这张图里很多点实际都是没有用的。所有$h(a_i)\le x$的点就是没有用的，它们都没有连边，都可以单独一组直接计入答案。可以预处理出每个$x$，$h(a_i)\le x$的点对答案的贡献，这样建图的时候就不用考虑这些点了。

另一方面，对于$h(a_i)>x$的点，如果有很多个点的$h(a_i)$相等，那么这些点都必须在同一组，其中$c_i$最大的那个可能计入贡献。不妨把它们当作一个点，这个点的$c_i$就是原来那些点$c_i$的最大值。

可以考虑按照$h(a_i)$把所有点分类，由于$h(a_i)\le sqrt(a_i)\le 200$，那么最多也就只有$200$类，也就是图上最多有$200$个点。而且枚举$x$也只需要枚举到$max\{h(a_i)\}$，这个时候建图应该可以AC此题了。代码就不放了。

但是这样复杂度是$O(a^\frac{3}{2})$，并不是最优复杂度，如果$a$的范围是$2\times 10^7$就没了。

可以考虑从$max\{h(a_i)\}$开始，从大到小枚举$x$。这样相当于在图上不断加边，连通块可以用并查集维护。具体实现可以在计算完$x$的答案之后，把所有$x$的倍数合并起来。时间复杂度$O(\sqrt alog^2a)$，低于线性复杂度，所以实际上复杂度的瓶颈是线性筛，总体复杂度应该是$O(n+m+max\{a_i\}+max\{b_i\})$。

完整代码

#include <cstdio>
#include <vector>
#define N 200000
#define M 20000001
#define R 201
#define L 40001
std::vector<int> pr;
int s[M], h[L]; char st[M], sm[M]; //int改成char极限卡内存
void prime() {
	for (int i = 2; i < M; i++) {
		if (!s[i]) {
			pr.push_back(i);
			s[i] = i;
			st[i] = sm[i] = 1;
			if (i < L) h[i] = 1;
		}
		for (int j : pr) {
			if (i*j >= M) break;
			s[i*j] = j;
			st[i*j] = (s[i] == j) ? st[i]+1 : 1;
			if (i*j < L) h[i*j] = (s[i] == j && st[i] & 1) ? h[i]*j : h[i];
			sm[i*j] = std::max(sm[i], st[i*j]);
			if (i % j == 0) break;
		}
	}
}
struct pair {int x, y; };
pair operator + (pair a, pair b) {
	return (pair) {a.x + b.x, a.y + b.y};
}
int n, m, a[N], b[N], mv[R], f[R], p[R];
pair co[R], ans[R], cnt;
int fa(int x) {
	return x == f[x] ? x : f[x] = fa(f[x]);
}
int main() {
	prime();
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++)
		scanf("%d", a+i);
	for (int i = 0; i < n; i++) {
		scanf("%d", b+i);
		a[i] = h[a[i]];
		b[i] = sm[b[i]];
		co[a[i]] = co[a[i]] + (pair) {1, b[i]};
		mv[a[i]] = std::max(mv[a[i]], b[i]);
	}
	for (int i = 2; i < R; i++)
		co[i] = co[i] + co[i-1];
	for (int i = R-1; i >= 2; i--) {
		ans[i] = co[i]+cnt;
		if (!mv[i]) continue;
		f[i] = i; p[i] = mv[i];
		cnt = cnt + (pair) {1, mv[i]};
		for (int j = 2; i*j < R; j++) if (mv[i*j]) {
			int x = fa(i), y = fa(i*j);
			if (x != y) {
				f[x] = y;
				cnt.x--;
				cnt.y -= std::min(p[x], p[y]);
				p[y] = std::max(p[x], p[y]);
			}
		}
	}
	while (m--) {
		int x; scanf("%d", &x);
		pair p = (x < R) ? ans[x] : co[R-1];
		printf("%d %d\n", p.x, p.y);
	}
}